package graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;


public class GraphUtil {
	
	public static <T> List<T> bfs(Graph<T> graph,T v,boolean checkCycle){
		Queue<T> vertexQueue = new LinkedList<T>();//待访问节点队列
		List<T> vistList = new ArrayList<T>();//已访问节点
		
		if(!graph.containsVertex(v)){
			throw new IllegalArgumentException("没有" + v + "对应的节点" );
		}
		
		graph.allUnVisted();//全部设置为为访问
		vertexQueue.add(v);
		
		T curr = null;
		Set<T> neighbors = null;
		
		while(!vertexQueue.isEmpty()){
			curr = vertexQueue.poll();
			
			graph.setState(curr, VertexState.VISITED);//设置为已访问
			vistList.add(curr);//加入已访问列表
			
			neighbors = graph.getNeighbors(curr);
			for(T neighbor : neighbors){
				VertexState state = graph.getState(neighbor);
				if( state == VertexState.UNVISITED){//未访问，者加入待访问列表
					graph.setState(neighbor, VertexState.PASSED);//设为已经过
					vertexQueue.add(neighbor);
				}else{
					if(state == VertexState.PASSED && checkCycle){
						throw new IllegalStateException("存在环");
					}
				}
			}
		}
		
		return vistList;
	}
	/**
	 * 深度优先遍历
	 * @param <T>
	 * @param graph
	 * @param v
	 * @param checkCycle
	 * @return
	 */
	public static <T> List<T> dfs(Graph<T> graph, T v,boolean checkCycle){
		graph.allUnVisted();
		List<T> vList = new ArrayList<T>();
		dfsHandler(graph,v,checkCycle,vList);
		return vList;
	}
	/**
	 * 图所有节点的遍历
	 * @param <T>
	 * @param graph
	 * @return
	 */
	public static<T> List<T> visitGraph(Graph<T> graph){
		List<T> vList = new ArrayList<T>();
		graph.allUnVisted();
		for(T v : graph.vertexSet()){
			if(graph.getState(v) == VertexState.UNVISITED){
				dfsHandler(graph,v,false,vList);
			}
		}
		return vList;
	}
	/**
	 * 测试图是否有环
	 * true 有环
	 * false 无环
	 */
	public static<T> boolean checkCycle(Graph<T> graph){
		graph.allUnVisted();
		List<T> vList = new ArrayList<T>();
		for(T v : graph.vertexSet()){
			try{
				dfsHandler(graph, v, true, vList);
			}catch (IllegalStateException e) {
				return true;
			}
		}
		return false;
	}
	public static<T> void dfsHandler(Graph<T> graph, T v,boolean checkCycle,List vList){
		Set<T> neighbors = null;
		if(!graph.containsVertex(v)){
			throw new IllegalStateException("不存在该顶点");
		}
		graph.setState(v, VertexState.PASSED);
		vList.add(v);
		
		neighbors = graph.getNeighbors(v);
		VertexState state = null;
		for(T neighbor : neighbors){
			state = graph.getState(neighbor);
			if(state == VertexState.UNVISITED){//未遍历，者将其状态设为已访问，然遍历
				dfsHandler(graph, neighbor, checkCycle, vList);
			}else if(state == VertexState.PASSED && checkCycle){//已经访问过，者存在一个环
				throw new IllegalStateException("存在环");
			}
		}
		graph.setState(v, VertexState.VISITED);//访问结束设为已访问
	}
	
}
